package problems.daily;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 886. 可能的二分法
 * <p>https://leetcode.cn/problems/possible-bipartition/</p>
 *
 * @author habitplus
 * @since 15:06, 2022/10/16
 */
public class DT886 {

    public boolean possibleBipartition(int n, int[][] dislikes) {
        int[] fa = new int[n + 1];
        Arrays.fill(fa, -1);
        List<Integer>[] g = new List[n + 1];
        for (int i = 0; i <= n; ++i) {
            g[i] = new ArrayList<>();
        }
        for (int[] p : dislikes) {
            g[p[0]].add(p[1]);
            g[p[1]].add(p[0]);
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < g[i].size(); ++j) {
                unit(g[i].get(0), g[i].get(j), fa);
                if (isConnect(i, g[i].get(j), fa)) {
                    return false;
                }
            }
        }
        return true;
    }

    public void unit(int x, int y, int[] fa) {
        x = findFa(x, fa);
        y = findFa(y, fa);

        // 已经在同一个集合内
        if (x == y) return;
        int tmp;

        // 确保 fa[x] > fa[y]
        if (fa[x] < fa[y]) {
            tmp = x;
            x = y;
            y = tmp;
        }

        fa[x] += fa[y];
        fa[y] = x;
    }

    public boolean isConnect(int x, int y, int[] fa) {
        x = findFa(x, fa);
        y = findFa(y, fa);
        return x == y;
    }

    public int findFa(int x, int[] fa) {
        while (fa[x] >= 0) x = fa[x];
        return x;
    }
}
